package chapter_03;


public class BubbleSort {
    // 冒泡排序
    /*
    不变性：在许多算法中，有些条件在算法执行时是不变的。这些条件被称为不变性。认识不变性对理解
    算法是有用的。在一定的情况下它们对调试也有用；可以反复地检查不变形是否为真，如果不是的话就
    标记为出错。冒泡排序的不变性是指out右边的所有数据项为有序。在算法的整个运行过程中这个条件
    始终为真。（在第一趟排序开始前，尚未排序，因为out开始时在数据项的最右边，没有数据项在out的
    右边。）
     */
    protected long[] a;
    protected int nElems;

    public BubbleSort(int max) {
        a = new long[max];
        nElems = 0;
    }

    public void insert(long value) {
        a[nElems++] = value;
    }

    public void display() {
        for (int j = 0; j < nElems; j++)
            System.out.print(a[j] + " ");
        System.out.println("");
    }

    public void sort() {
        /*
        这个算法的思路是要将最小的数据项放在数组的最开始（数组下标为0），并将最大的数据项放在
        数组的最后（数组下标为nElems-1）。外层for循环的计数器out从数组的最后开始，即out等于
        nElems-1，每经过一次循环out减一。下标大于out的数据项都已经是排好序的了。变量out在每
        完成一次内部循环（计数器为in）后就左移一位，因此算法就不再处理那些已经排好序的数了。
        内层for循环计数器in从数组的最开始算起，即in=0，每完成一次内部循环体加一，当它等于out
        时结束一次循环。在内层for循环体中，数组下标为in和in+1的两个数据项进行比较，如果下标为
        in的数据项大于下标为in+1的数据项，则交换两个数据项。
         */
        int out, in;
        for (out = nElems - 1; out > 1; out--)
            for (in = 0; in < out; in++)
                if (a[in] > a[in + 1])
                    swap(in, in + 1);
    }

    public void swap(int one, int two) {
        long temp = a[one];
        a[one] = a[two];
        a[two] = temp;
    }

    public static void main(String[] args) {
        int maxSize = 10;
        BubbleSort arr;
        arr = new BubbleSort(maxSize);

        arr.insert(77);
        arr.insert(99);
        arr.insert(44);
        arr.insert(55);
        arr.insert(22);
        arr.insert(88);
        arr.insert(11);
        arr.insert(00);
        arr.insert(66);
        arr.insert(33);
        arr.display();
        arr.sort();
        arr.display();
    }
}
